<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"/><title>1. 草履虫都能看懂的并查集</title><style>
/* cspell:disable-file */
/* webkit printing magic: print all background colors */
html {
	-webkit-print-color-adjust: exact;
}
* {
	box-sizing: border-box;
	-webkit-print-color-adjust: exact;
}

html,
body {
	margin: 0;
	padding: 0;
}
@media only screen {
	body {
		margin: 2em auto;
		max-width: 900px;
		color: rgb(55, 53, 47);
	}
}

body {
	line-height: 1.5;
	white-space: pre-wrap;
}

a,
a.visited {
	color: inherit;
	text-decoration: underline;
}

.pdf-relative-link-path {
	font-size: 80%;
	color: #444;
}

h1,
h2,
h3 {
	letter-spacing: -0.01em;
	line-height: 1.2;
	font-weight: 600;
	margin-bottom: 0;
}

.page-title {
	font-size: 2.5rem;
	font-weight: 700;
	margin-top: 0;
	margin-bottom: 0.75em;
}

h1 {
	font-size: 1.875rem;
	margin-top: 1.875rem;
}

h2 {
	font-size: 1.5rem;
	margin-top: 1.5rem;
}

h3 {
	font-size: 1.25rem;
	margin-top: 1.25rem;
}

.source {
	border: 1px solid #ddd;
	border-radius: 3px;
	padding: 1.5em;
	word-break: break-all;
}

.callout {
	border-radius: 3px;
	padding: 1rem;
}

figure {
	margin: 1.25em 0;
	page-break-inside: avoid;
}

figcaption {
	opacity: 0.5;
	font-size: 85%;
	margin-top: 0.5em;
}

mark {
	background-color: transparent;
}

.indented {
	padding-left: 1.5em;
}

hr {
	background: transparent;
	display: block;
	width: 100%;
	height: 1px;
	visibility: visible;
	border: none;
	border-bottom: 1px solid rgba(55, 53, 47, 0.09);
}

img {
	max-width: 100%;
}

@media only print {
	img {
		max-height: 100vh;
		object-fit: contain;
	}
}

@page {
	margin: 1in;
}

.collection-content {
	font-size: 0.875rem;
}

.column-list {
	display: flex;
	justify-content: space-between;
}

.column {
	padding: 0 1em;
}

.column:first-child {
	padding-left: 0;
}

.column:last-child {
	padding-right: 0;
}

.table_of_contents-item {
	display: block;
	font-size: 0.875rem;
	line-height: 1.3;
	padding: 0.125rem;
}

.table_of_contents-indent-1 {
	margin-left: 1.5rem;
}

.table_of_contents-indent-2 {
	margin-left: 3rem;
}

.table_of_contents-indent-3 {
	margin-left: 4.5rem;
}

.table_of_contents-link {
	text-decoration: none;
	opacity: 0.7;
	border-bottom: 1px solid rgba(55, 53, 47, 0.18);
}

table,
th,
td {
	border: 1px solid rgba(55, 53, 47, 0.09);
	border-collapse: collapse;
}

table {
	border-left: none;
	border-right: none;
}

th,
td {
	font-weight: normal;
	padding: 0.25em 0.5em;
	line-height: 1.5;
	min-height: 1.5em;
	text-align: left;
}

th {
	color: rgba(55, 53, 47, 0.6);
}

ol,
ul {
	margin: 0;
	margin-block-start: 0.6em;
	margin-block-end: 0.6em;
}

li > ol:first-child,
li > ul:first-child {
	margin-block-start: 0.6em;
}

ul > li {
	list-style: disc;
}

ul.to-do-list {
	text-indent: -1.7em;
}

ul.to-do-list > li {
	list-style: none;
}

.to-do-children-checked {
	text-decoration: line-through;
	opacity: 0.375;
}

ul.toggle > li {
	list-style: none;
}

ul {
	padding-inline-start: 1.7em;
}

ul > li {
	padding-left: 0.1em;
}

ol {
	padding-inline-start: 1.6em;
}

ol > li {
	padding-left: 0.2em;
}

.mono ol {
	padding-inline-start: 2em;
}

.mono ol > li {
	text-indent: -0.4em;
}

.toggle {
	padding-inline-start: 0em;
	list-style-type: none;
}

/* Indent toggle children */
.toggle > li > details {
	padding-left: 1.7em;
}

.toggle > li > details > summary {
	margin-left: -1.1em;
}

.selected-value {
	display: inline-block;
	padding: 0 0.5em;
	background: rgba(206, 205, 202, 0.5);
	border-radius: 3px;
	margin-right: 0.5em;
	margin-top: 0.3em;
	margin-bottom: 0.3em;
	white-space: nowrap;
}

.collection-title {
	display: inline-block;
	margin-right: 1em;
}

.simple-table {
	margin-top: 1em;
	font-size: 0.875rem;
	empty-cells: show;
}
.simple-table td {
	height: 29px;
	min-width: 120px;
}

.simple-table th {
	height: 29px;
	min-width: 120px;
}

.simple-table-header-color {
	background: rgb(247, 246, 243);
	color: black;
}
.simple-table-header {
	font-weight: 500;
}

time {
	opacity: 0.5;
}

.icon {
	display: inline-block;
	max-width: 1.2em;
	max-height: 1.2em;
	text-decoration: none;
	vertical-align: text-bottom;
	margin-right: 0.5em;
}

img.icon {
	border-radius: 3px;
}

.user-icon {
	width: 1.5em;
	height: 1.5em;
	border-radius: 100%;
	margin-right: 0.5rem;
}

.user-icon-inner {
	font-size: 0.8em;
}

.text-icon {
	border: 1px solid #000;
	text-align: center;
}

.page-cover-image {
	display: block;
	object-fit: cover;
	width: 100%;
	max-height: 30vh;
}

.page-header-icon {
	font-size: 3rem;
	margin-bottom: 1rem;
}

.page-header-icon-with-cover {
	margin-top: -0.72em;
	margin-left: 0.07em;
}

.page-header-icon img {
	border-radius: 3px;
}

.link-to-page {
	margin: 1em 0;
	padding: 0;
	border: none;
	font-weight: 500;
}

p > .user {
	opacity: 0.5;
}

td > .user,
td > time {
	white-space: nowrap;
}

input[type="checkbox"] {
	transform: scale(1.5);
	margin-right: 0.6em;
	vertical-align: middle;
}

p {
	margin-top: 0.5em;
	margin-bottom: 0.5em;
}

.image {
	border: none;
	margin: 1.5em 0;
	padding: 0;
	border-radius: 0;
	text-align: center;
}

.code,
code {
	background: rgba(135, 131, 120, 0.15);
	border-radius: 3px;
	padding: 0.2em 0.4em;
	border-radius: 3px;
	font-size: 85%;
	tab-size: 2;
}

code {
	color: #eb5757;
}

.code {
	padding: 1.5em 1em;
}

.code-wrap {
	white-space: pre-wrap;
	word-break: break-all;
}

.code > code {
	background: none;
	padding: 0;
	font-size: 100%;
	color: inherit;
}

blockquote {
	font-size: 1.25em;
	margin: 1em 0;
	padding-left: 1em;
	border-left: 3px solid rgb(55, 53, 47);
}

.bookmark {
	text-decoration: none;
	max-height: 8em;
	padding: 0;
	display: flex;
	width: 100%;
	align-items: stretch;
}

.bookmark-title {
	font-size: 0.85em;
	overflow: hidden;
	text-overflow: ellipsis;
	height: 1.75em;
	white-space: nowrap;
}

.bookmark-text {
	display: flex;
	flex-direction: column;
}

.bookmark-info {
	flex: 4 1 180px;
	padding: 12px 14px 14px;
	display: flex;
	flex-direction: column;
	justify-content: space-between;
}

.bookmark-image {
	width: 33%;
	flex: 1 1 180px;
	display: block;
	position: relative;
	object-fit: cover;
	border-radius: 1px;
}

.bookmark-description {
	color: rgba(55, 53, 47, 0.6);
	font-size: 0.75em;
	overflow: hidden;
	max-height: 4.5em;
	word-break: break-word;
}

.bookmark-href {
	font-size: 0.75em;
	margin-top: 0.25em;
}

.sans { font-family: ui-sans-serif, -apple-system, BlinkMacSystemFont, "Segoe UI", Helvetica, "Apple Color Emoji", Arial, sans-serif, "Segoe UI Emoji", "Segoe UI Symbol"; }
.code { font-family: "SFMono-Regular", Menlo, Consolas, "PT Mono", "Liberation Mono", Courier, monospace; }
.serif { font-family: Lyon-Text, Georgia, ui-serif, serif; }
.mono { font-family: iawriter-mono, Nitti, Menlo, Courier, monospace; }
.pdf .sans { font-family: Inter, ui-sans-serif, -apple-system, BlinkMacSystemFont, "Segoe UI", Helvetica, "Apple Color Emoji", Arial, sans-serif, "Segoe UI Emoji", "Segoe UI Symbol", 'Twemoji', 'Noto Color Emoji', 'Noto Sans CJK JP'; }
.pdf:lang(zh-CN) .sans { font-family: Inter, ui-sans-serif, -apple-system, BlinkMacSystemFont, "Segoe UI", Helvetica, "Apple Color Emoji", Arial, sans-serif, "Segoe UI Emoji", "Segoe UI Symbol", 'Twemoji', 'Noto Color Emoji', 'Noto Sans CJK SC'; }
.pdf:lang(zh-TW) .sans { font-family: Inter, ui-sans-serif, -apple-system, BlinkMacSystemFont, "Segoe UI", Helvetica, "Apple Color Emoji", Arial, sans-serif, "Segoe UI Emoji", "Segoe UI Symbol", 'Twemoji', 'Noto Color Emoji', 'Noto Sans CJK TC'; }
.pdf:lang(ko-KR) .sans { font-family: Inter, ui-sans-serif, -apple-system, BlinkMacSystemFont, "Segoe UI", Helvetica, "Apple Color Emoji", Arial, sans-serif, "Segoe UI Emoji", "Segoe UI Symbol", 'Twemoji', 'Noto Color Emoji', 'Noto Sans CJK KR'; }
.pdf .code { font-family: Source Code Pro, "SFMono-Regular", Menlo, Consolas, "PT Mono", "Liberation Mono", Courier, monospace, 'Twemoji', 'Noto Color Emoji', 'Noto Sans Mono CJK JP'; }
.pdf:lang(zh-CN) .code { font-family: Source Code Pro, "SFMono-Regular", Menlo, Consolas, "PT Mono", "Liberation Mono", Courier, monospace, 'Twemoji', 'Noto Color Emoji', 'Noto Sans Mono CJK SC'; }
.pdf:lang(zh-TW) .code { font-family: Source Code Pro, "SFMono-Regular", Menlo, Consolas, "PT Mono", "Liberation Mono", Courier, monospace, 'Twemoji', 'Noto Color Emoji', 'Noto Sans Mono CJK TC'; }
.pdf:lang(ko-KR) .code { font-family: Source Code Pro, "SFMono-Regular", Menlo, Consolas, "PT Mono", "Liberation Mono", Courier, monospace, 'Twemoji', 'Noto Color Emoji', 'Noto Sans Mono CJK KR'; }
.pdf .serif { font-family: PT Serif, Lyon-Text, Georgia, ui-serif, serif, 'Twemoji', 'Noto Color Emoji', 'Noto Serif CJK JP'; }
.pdf:lang(zh-CN) .serif { font-family: PT Serif, Lyon-Text, Georgia, ui-serif, serif, 'Twemoji', 'Noto Color Emoji', 'Noto Serif CJK SC'; }
.pdf:lang(zh-TW) .serif { font-family: PT Serif, Lyon-Text, Georgia, ui-serif, serif, 'Twemoji', 'Noto Color Emoji', 'Noto Serif CJK TC'; }
.pdf:lang(ko-KR) .serif { font-family: PT Serif, Lyon-Text, Georgia, ui-serif, serif, 'Twemoji', 'Noto Color Emoji', 'Noto Serif CJK KR'; }
.pdf .mono { font-family: PT Mono, iawriter-mono, Nitti, Menlo, Courier, monospace, 'Twemoji', 'Noto Color Emoji', 'Noto Sans Mono CJK JP'; }
.pdf:lang(zh-CN) .mono { font-family: PT Mono, iawriter-mono, Nitti, Menlo, Courier, monospace, 'Twemoji', 'Noto Color Emoji', 'Noto Sans Mono CJK SC'; }
.pdf:lang(zh-TW) .mono { font-family: PT Mono, iawriter-mono, Nitti, Menlo, Courier, monospace, 'Twemoji', 'Noto Color Emoji', 'Noto Sans Mono CJK TC'; }
.pdf:lang(ko-KR) .mono { font-family: PT Mono, iawriter-mono, Nitti, Menlo, Courier, monospace, 'Twemoji', 'Noto Color Emoji', 'Noto Sans Mono CJK KR'; }
.highlight-default {
	color: rgba(55, 53, 47, 1);
}
.highlight-gray {
	color: rgba(120, 119, 116, 1);
	fill: rgba(120, 119, 116, 1);
}
.highlight-brown {
	color: rgba(159, 107, 83, 1);
	fill: rgba(159, 107, 83, 1);
}
.highlight-orange {
	color: rgba(217, 115, 13, 1);
	fill: rgba(217, 115, 13, 1);
}
.highlight-yellow {
	color: rgba(203, 145, 47, 1);
	fill: rgba(203, 145, 47, 1);
}
.highlight-teal {
	color: rgba(68, 131, 97, 1);
	fill: rgba(68, 131, 97, 1);
}
.highlight-blue {
	color: rgba(51, 126, 169, 1);
	fill: rgba(51, 126, 169, 1);
}
.highlight-purple {
	color: rgba(144, 101, 176, 1);
	fill: rgba(144, 101, 176, 1);
}
.highlight-pink {
	color: rgba(193, 76, 138, 1);
	fill: rgba(193, 76, 138, 1);
}
.highlight-red {
	color: rgba(212, 76, 71, 1);
	fill: rgba(212, 76, 71, 1);
}
.highlight-gray_background {
	background: rgba(241, 241, 239, 1);
}
.highlight-brown_background {
	background: rgba(244, 238, 238, 1);
}
.highlight-orange_background {
	background: rgba(251, 236, 221, 1);
}
.highlight-yellow_background {
	background: rgba(251, 243, 219, 1);
}
.highlight-teal_background {
	background: rgba(237, 243, 236, 1);
}
.highlight-blue_background {
	background: rgba(231, 243, 248, 1);
}
.highlight-purple_background {
	background: rgba(244, 240, 247, 0.8);
}
.highlight-pink_background {
	background: rgba(249, 238, 243, 0.8);
}
.highlight-red_background {
	background: rgba(253, 235, 236, 1);
}
.block-color-default {
	color: inherit;
	fill: inherit;
}
.block-color-gray {
	color: rgba(120, 119, 116, 1);
	fill: rgba(120, 119, 116, 1);
}
.block-color-brown {
	color: rgba(159, 107, 83, 1);
	fill: rgba(159, 107, 83, 1);
}
.block-color-orange {
	color: rgba(217, 115, 13, 1);
	fill: rgba(217, 115, 13, 1);
}
.block-color-yellow {
	color: rgba(203, 145, 47, 1);
	fill: rgba(203, 145, 47, 1);
}
.block-color-teal {
	color: rgba(68, 131, 97, 1);
	fill: rgba(68, 131, 97, 1);
}
.block-color-blue {
	color: rgba(51, 126, 169, 1);
	fill: rgba(51, 126, 169, 1);
}
.block-color-purple {
	color: rgba(144, 101, 176, 1);
	fill: rgba(144, 101, 176, 1);
}
.block-color-pink {
	color: rgba(193, 76, 138, 1);
	fill: rgba(193, 76, 138, 1);
}
.block-color-red {
	color: rgba(212, 76, 71, 1);
	fill: rgba(212, 76, 71, 1);
}
.block-color-gray_background {
	background: rgba(241, 241, 239, 1);
}
.block-color-brown_background {
	background: rgba(244, 238, 238, 1);
}
.block-color-orange_background {
	background: rgba(251, 236, 221, 1);
}
.block-color-yellow_background {
	background: rgba(251, 243, 219, 1);
}
.block-color-teal_background {
	background: rgba(237, 243, 236, 1);
}
.block-color-blue_background {
	background: rgba(231, 243, 248, 1);
}
.block-color-purple_background {
	background: rgba(244, 240, 247, 0.8);
}
.block-color-pink_background {
	background: rgba(249, 238, 243, 0.8);
}
.block-color-red_background {
	background: rgba(253, 235, 236, 1);
}
.select-value-color-pink { background-color: rgba(245, 224, 233, 1); }
.select-value-color-purple { background-color: rgba(232, 222, 238, 1); }
.select-value-color-green { background-color: rgba(219, 237, 219, 1); }
.select-value-color-gray { background-color: rgba(227, 226, 224, 1); }
.select-value-color-opaquegray { background-color: rgba(255, 255, 255, 0.0375); }
.select-value-color-orange { background-color: rgba(250, 222, 201, 1); }
.select-value-color-brown { background-color: rgba(238, 224, 218, 1); }
.select-value-color-red { background-color: rgba(255, 226, 221, 1); }
.select-value-color-yellow { background-color: rgba(253, 236, 200, 1); }
.select-value-color-blue { background-color: rgba(211, 229, 239, 1); }

.checkbox {
	display: inline-flex;
	vertical-align: text-bottom;
	width: 16;
	height: 16;
	background-size: 16px;
	margin-left: 2px;
	margin-right: 5px;
}

.checkbox-on {
	background-image: url("data:image/svg+xml;charset=UTF-8,%3Csvg%20width%3D%2216%22%20height%3D%2216%22%20viewBox%3D%220%200%2016%2016%22%20fill%3D%22none%22%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F2000%2Fsvg%22%3E%0A%3Crect%20width%3D%2216%22%20height%3D%2216%22%20fill%3D%22%2358A9D7%22%2F%3E%0A%3Cpath%20d%3D%22M6.71429%2012.2852L14%204.9995L12.7143%203.71436L6.71429%209.71378L3.28571%206.2831L2%207.57092L6.71429%2012.2852Z%22%20fill%3D%22white%22%2F%3E%0A%3C%2Fsvg%3E");
}

.checkbox-off {
	background-image: url("data:image/svg+xml;charset=UTF-8,%3Csvg%20width%3D%2216%22%20height%3D%2216%22%20viewBox%3D%220%200%2016%2016%22%20fill%3D%22none%22%20xmlns%3D%22http%3A%2F%2Fwww.w3.org%2F2000%2Fsvg%22%3E%0A%3Crect%20x%3D%220.75%22%20y%3D%220.75%22%20width%3D%2214.5%22%20height%3D%2214.5%22%20fill%3D%22white%22%20stroke%3D%22%2336352F%22%20stroke-width%3D%221.5%22%2F%3E%0A%3C%2Fsvg%3E");
}
	
</style></head><body><article id="0b174f5e-f857-46e4-984a-6f0e547f60f4" class="page sans"><header><div class="page-header-icon undefined"><span class="icon">🤠</span></div><h1 class="page-title">1. 草履虫都能看懂的并查集</h1></header><div class="page-body"><h2 id="7f5709e3-19c6-42dd-b846-00c4b1506703" class="">动态连通性<strong><strong>（Dynamic Connectivity）</strong></strong></h2><figure id="07608ae2-6b24-4282-82a1-265d1d7aba05"><a href="https://www.bilibili.com/video/BV1Jt411P77c?p=2" class="bookmark source"><div class="bookmark-info"><div class="bookmark-text"><div class="bookmark-title">01_dynamic-connectivity 动态连通性_哔哩哔哩_bilibili</div><div class="bookmark-description">01_dynamic-connectivity 动态连通性是普林斯顿大学丨算法第四版 Princeton University 丨 Algorithms Part 1的第2集视频，该合集共计59集，视频收藏或关注UP主，及时了解更多相关视频内容。</div></div><div class="bookmark-href"><img src="https://www.bilibili.com/favicon.ico" class="icon bookmark-icon"/>https://www.bilibili.com/video/BV1Jt411P77c?p=2</div></div><img src="http://i0.hdslb.com/bfs/archive/57e927b817053b87c1005cfdee8dc9cdccf69310.png" class="bookmark-image"/></a></figure><p id="50bcca4f-4733-4dc3-894d-89b5ec35ed66" class="">我们定义有 N 个相互独立的节点，并提供以下两个操作。</p><p id="460e0a39-6c9b-48c2-9a14-efe1ea40cda2" class=""><strong>连接：将两个节点进行连接。</strong></p><p id="7cb84df0-a069-440a-b878-4327ae7a52de" class=""><strong>是否连通：判断两个节点是否连通</strong></p><figure id="193cd010-708b-40e5-91b9-10b2ae1c67d0" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled.png"><img style="width:1976px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled.png"/></a></figure><p id="e85b8758-ce39-4ef0-9bb9-3e7ccd684c58" class="">如图，初始状态下，每一个节点都是单独独立的节点。我们先后连接 <code>节点3</code> 和 <code>节点4</code> 、<code>节点3</code> 和 <code>节点8</code>、<code>节点6</code> 和 <code>节点5</code>、<code>节点9</code> 和 <code>节点4</code>、<code>节点2</code> 和 <code>节点1</code>、<code>节点5</code> 和 <code>节点0</code>、<code>节点2</code> 和 <code>节点7</code>、<code>节点6</code> 和 <code>节点1</code>、<code>节点0</code> 和 <code>节点1</code> ，此时我们去判断 <code>节点0</code> 和 <code>节点7</code> 是否连通。在执行完多个节点连接的操作后，去判断节点是否连通的问题就是动态连通性问题。</p><figure id="5bdfb1da-9dbc-4d53-8eb4-a0cd37a58788" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%201.png"><img style="width:1354px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%201.png"/></a></figure><p id="a6db8b0e-7d0f-4eef-84b5-fa44f943a1df" class="">我们会运用到什么场景？</p><p id="74f9a7a8-a8ad-437c-8a0c-e8b4e98ce84e" class="">两个国家是不是在同一片大陆</p><p id="c95756ac-67a9-47e7-a5dc-7d37b7fd30a7" class="">社交关系的两个人</p><h2 id="fc45f41c-6850-4d07-b271-28dd11c27aab" class="">什么是并查集？</h2><p id="8529867a-f53d-46a5-860d-96c6aaac2ba8" class="">并查集就是<strong>合并（Union）、查询（Find）</strong></p><p id="c30c4562-d150-4028-b62e-ec6f2b465f01" class=""><strong>合并（Union）</strong>：把两个不相交的集合合并为一个集合。</p><p id="7977ba19-2d7c-4797-b493-ddbd621c07eb" class=""><strong>查询（Find）</strong>：查询两个元素是否在同一个集合中。</p><p id="f1eb761c-75c6-4f2f-8326-c87d7a1bd037" class="">对于动态连通性问题，我们就可以使用并查集来解决。</p><h2 id="4c18475a-d261-4067-adeb-8a880ac235c3" class="">建立模型</h2><p id="6755eb92-1d6b-48a8-bf91-6f1d73edfa13" class="">我们使用并查集的思想，去解决动态连通性问题。</p><ol type="1" id="d9812ff4-76e5-4335-866d-8962d826b504" class="numbered-list" start="1"><li>我们可以把连通的节点放入到同一个集合中。</li></ol><ol type="1" id="5995f5da-ac29-41a1-a36a-f8729ad8260c" class="numbered-list" start="2"><li>当我门连接两个不连通的节点时，就将这两个节点所在的集合合并成一个集合。</li></ol><ol type="1" id="3968bf3d-8a64-48eb-8eb9-2094485273ff" class="numbered-list" start="3"><li>当查询两个节点是否连通的时候，只用判断这两个节点是否在一个集合中即可。</li></ol><figure id="7655d0da-a85f-44fa-a2a7-7135352ae1fa" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%202.png"><img style="width:1824px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%202.png"/></a></figure><p id="744f27ec-585a-410f-8156-a93e623dad1d" class="">我们抽象如下的接口，实现这个接口以完成不同并查集实现的算法。</p><pre id="6a6cd41d-c02e-4422-9880-bf0f132648a1" class="code code-wrap"><code>public interface IDynamicConnectivity {
    void union(int p,int q);
    boolean connected(int p,int q);
}</code></pre><p id="590a40e9-7e26-416d-a0f9-f0cc2ebee3a1" class="">
</p><h2 id="8f9c8e5f-09b5-4c3d-b2b7-01756962574e" class="">Quick-Find 快速查询 </h2><p id="77f1a5f7-68b6-451f-b3b6-5d89a4b7ae59" class="">我们使用一个 <code>int</code> 数组来表示每一个节点所在的集合。如 <code>节点0</code> 所在的集合标记由 <code>id[0]</code> 来存储。由于初始状态下，每一个节点都是一个独立的节点，那么 N 个节点就需要 N 个集合，<code>id</code> 数组的初始化就显而易见了即 <code>id[i] = i</code> 。</p><pre id="febbb561-6fa5-48be-bd5b-5efe882952ea" class="code code-wrap"><code>public class QuickFind implements IDynamicConnectivity {
	private int[] id;
	public QuickFind(int size) {
    id = new int[size];
    for (int i = 0; i &lt; id.length; i++) {
        id[i] = i;
    }
	}
}</code></pre><blockquote id="5c87f5da-410f-4518-b736-6034b2b69a1c" class="">tips: 其实这里等式的右边半只要不重复皆可，它就是集合的唯一标识，不一定需要等于 <code>i</code>，如果你喜欢 <code>id[i] = i + 114514</code> 都是可以的。</blockquote><figure id="db59ef6c-b721-4e9e-9166-f86893944981" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%203.png"><img style="width:964px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%203.png"/></a></figure><p id="2c16ea55-f9b6-4fc5-9717-a5a6c55c3736" class="">当我们判断 <code>节点3</code> 和 <code>节点9</code> 是否在一个集合的时候，只需要判断 <code>id[3] == id[9]</code> 即可。那 <code>connected</code> 方法的实现就很简单明了了，而此方法也因此得名 <code>Quick-Find</code> ，因为他查询仅需要 O1 的时间复杂度。</p><pre id="66444edd-f559-4fc6-8a15-dcbda2f6e17f" class="code code-wrap"><code>@Override
public boolean connected(int p, int q) {
    return id[p] == id[q];
}</code></pre><p id="152470de-36ad-4472-88b6-f19ffb74d49e" class="">那是用这个模型合并两个集合的方法就显而易见了，只需要将需要合并的两个集合的编号 <code>id[node]</code> 设置为其中一个集合的编号 <code>id[node]</code> 即可。现在我们假设连通 <code>p node</code> 和 <code>q node</code> ，他们所对应的集合的编号是 <code>pid</code> 和 <code>qid</code> ，当 <code>id[i] == pid</code> 将 <code>id[i]</code> 设置为 <code>qid</code>  。所以得到<code>union</code> 方法的实现如下。</p><pre id="8ec9e139-cab9-416d-9a0d-0f00220e25f6" class="code code-wrap"><code>@Override
public void union(int p, int q) {
    int pid = id[p];
    int qid = id[q];
    for (int i = 0; i &lt; id.length; i++) {
        if (id[i] == pid) {
            id[i] = qid;
        }
    }
}</code></pre><blockquote id="6396e9b0-8036-49e2-b95d-b5c5236a006e" class="">tips: 这里很容易犯一个错，那就是 <code>id[i] == pid</code> 这里，有人可能会写成 <code>id[i] == id[p]</code> ，这显然是错误的。因为过程中会修改到 <code>id[p] = qid</code> 那么 <code>id[p]</code> 之后的节点就变成判断 <code>id[i] == qid</code>。</blockquote><h3 id="e62d86e4-9729-406c-9aa2-7de8d7b5b462" class="">复杂度分析</h3><p id="8eb3d4e6-11d7-45f2-adbc-b48a13014068" class="">空间复杂度：由于需要 N 个空间存储每个节点所在的集合，所以空间复杂度就是 On</p><p id="db39ed6a-fe7a-4de7-ae8e-28424472557a" class="">时间复杂度分析如下</p><table id="7dc1b096-997d-4c31-a4b0-37cb2f59cbdc" class="simple-table"><tbody><tr id="d8f868e5-ac59-43ad-ba9f-98d6662b5e41"><td id="bwCx" class="">Init</td><td id="gU:E" class="">Union</td><td id="VmKf" class="">Find</td></tr><tr id="40e01016-20f1-44e0-9011-464fc7254a68"><td id="bwCx" class="">N</td><td id="gU:E" class="">N</td><td id="VmKf" class="">1</td></tr></tbody></table><p id="82b2cd74-24cd-49b3-9cc6-b37c83a73034" class="">Init：初始化数组需要进行遍历时间复杂度为 On</p><p id="ff9888ed-f826-4624-ac49-7dff5cfded22" class="">Union：合并集合也需要遍历所以时间复杂度为 On</p><p id="40cecfeb-a840-4c36-8efb-08387baa9e5f" class="">Find: 查询操作通过数组下标直接对比得出，时间复杂度为 O1</p><h3 id="b41f7a03-a7a6-4f70-a186-498f3b17b827" class="">总结</h3><p id="f562ac58-c522-42c6-ba7c-36ebf53ed4a8" class=""><code>Quick-Find</code> 实现顾名思义，查询很快，他能在 O1 的时间复杂度中获取到结果，但所带来的代价就是 <code>Union</code> 操作的时间复杂度很慢，当我们数组元素非常多时 N 会线性增长。</p><pre id="b142b9eb-c60c-47ad-a4e6-6aaada20d6a4" class="code code-wrap"><code>public class QuickFind implements IDynamicConnectivity{
    private int[] id;
    public QuickFind(int size) {
        id = new int[size];
        for (int i = 0; i &lt; id.length; i++) {
            id[i] = i;
        }
    }

    @Override
		// On的查找时间
		public void union(int p, int q) {
        int pid = id[p];
        int qid = id[q];
        for (int i = 0; i &lt; id.length; i++) {
            if (id[i] == pid) {
                id[i] = qid;
            }
        }
    }

    @Override
		// O1的比较时间
		public boolean connected(int p, int q) {
        return id[p] == id[q];
    }
}
</code></pre><p id="229c50ee-6f27-4196-ae27-30dedf062589" class="">
</p><h2 id="082a0296-fca4-47e0-9805-803641b76755" class=""> Quick-Union</h2><p id="f6d6f736-d24f-4f50-aa0c-ec50e5616cff" class="">刚刚我们了解完了 <code>Quick-Find</code> 实现，如果我们面对的是一个 <code>Union</code> 操作频繁的场景，那么 <code>Quick-Find</code> 就无法体现出他的优势，我们需要更新我们的模型，以提高 <code>Union</code> 操作的效率。我们分析在 <code>Quick-Find</code> 中 <code>Union</code> 的实现。</p><pre id="2380b530-5e85-493c-a9e8-10b81c2b31e8" class="code"><code>@Override
public void union(int p, int q) {
    int pid = id[p];
    int qid = id[q];
    for (int i = 0; i &lt; id.length; i++) {
        if (id[i] == pid) {
            id[i] = qid;
        }
    }
}</code></pre><p id="e7ab7b0c-a074-490d-8eae-72f480528250" class="">可以发现，当我们仅仅连通两个节点的时候，他需要将某个节点所在集合中的所有元素都进行更新，这就是造成需要遍历的核心原因。</p><p id="d2ae1e97-af99-4fe3-ab8a-621ce70a7a74" class="">我们需要提出一个更高效的关系结构，以达到更新更少的节点。除去线性表这种存储结构，我们还能容易想到<strong>树</strong>这个更紧凑的数据结构。</p><h3 id="e16f6454-0c50-4da7-8626-47a9aa6a3f33" class="">把他们挂在树上</h3><figure id="e871760c-7084-4cdb-89e7-e804d600be23" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%204.png"><img style="width:384px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%204.png"/></a></figure><p id="e26c6f18-0806-4f50-8a57-e26338854bdf" class="">Find：当连通的节点都存储在一个树上，那么判断他们是否连通只需要判断他们的根节点是否为同一个。例如我们要判断 <code>节点2</code> 和 <code>节点3</code> 是否连通，只需要找到他们的根节点也就是 <code>节点9</code> ，因此可以判断他们连通。</p><p id="09155323-f444-477a-9460-53f0c9ee4a91" class="">Union：当我们要连通两个节点的时候，需要找寻到他们的根节点，并让某一个根节点成为另一个根节点的叶子结点。如将 <code>节点3</code> 和 <code>节点5</code> 连通，我们就需要把根节点为<code>节点9</code> 和 根节点为<code>节点6</code> 的两个树进行合并，合并成如下图所示的样子。</p><figure id="d7756c11-3039-459b-9980-0f971829f2f2" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%205.png"><img style="width:384px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%205.png"/></a></figure><h3 id="6410a85f-7301-4250-90f2-d6b08273a467" class="">把树捋顺了！！</h3><p id="fe6d4631-8aca-44c2-a39b-ec99573e5968" class="">我们怎么存储这个树结构也是一个学问，你或许写过如下所示的二叉树。</p><pre id="377c31c9-5419-4bd7-811a-47dcbe7708a3" class="code"><code>public class TreeNode {
		int value;
		TreeNode left;
		TreeNode right;
}</code></pre><p id="59d8b4c3-e35c-4346-8825-b7de72035d3a" class="">但我们或许可以换个思路，这种数据结构是由父节点查找到子节点，自顶向下的。而我们要连通的两个节点，可能是两个叶子结点，这种数据结构我们无法向上查找。所以需要用子节点查询父节点的数据结构。</p><pre id="e9946064-f75d-4f2d-957a-28ab6802c196" class="code"><code>public class TreeNode {
		int value;
		TreeNode father;
}</code></pre><p id="5df0656e-2ff6-4637-9a90-1d86476ad56c" class="">这样我们就可以查询到该节点的父节点了。如果这个节点的父节点就是他自己，则说明他是这个树的根节点。</p><p id="c81d7e5b-f897-4906-abd5-87b6c954ecb8" class="">而最后我们可以通过链表模拟树的方式，来简化这个树的存储。依然是用一个 <code>int[] id</code> 数组，我们使用 <code>id 数组</code> 存储每个节点的父节点，也就是 <code>节点i</code> 的父节点为 <code>id[i]</code> 。如何在这个数组中获取到 <code>节点i</code> 的 <code>根节点</code> 呢？一直通过这个节点向上查询，直到某个节点的父节点是他本身，那么这个节点就是 <code>节点i</code> 的 <code>根节点</code> ，即 <code>id[id[…id[i]…]]</code> 就是 <code>节点i</code> 的 <code>根节点</code> 。下图展示的就是这些节点集合在 <code>id数组</code> 中的表示方式。</p><figure id="cf0260b8-a0ea-4a36-bee0-1ebf3f2f8299" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%205.png"><img style="width:384px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%205.png"/></a></figure><figure id="51ced5d5-4aa2-4a0f-b24c-b0628ba29e0a" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%206.png"><img style="width:384px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%206.png"/></a></figure><p id="81e1df01-7ba5-45ae-8ed8-e5da6d8c7fe8" class="">初始化，由于每个节点最开始的时候，都是一个单独的集合，所以每个节点都是根节点，因此需要让 <code>id[i] = i</code> ，则可以让每一个节点的父节点是自己了。</p><pre id="ca8c0e9f-8015-4968-857b-20741d7b17c1" class="code code-wrap"><code>public QuickUnion(int size) {
    id = new int[size];
    for (int i = 0; i &lt; id.length; i++) {
        id[i] = i;
    }
}</code></pre><blockquote id="2ac7510b-bda5-4a5c-897f-ea34d96837e1" class="">tips: 与 Quick-Find 不同，这里 <code>id[i]</code> 不再是单纯的标记，他需要承接节点的关系。</blockquote><p id="3c7dc530-382a-4996-a45a-a83a789bd74b" class="">我们再复习一遍在树上的 Union &amp; Find</p><ul id="8a3fd0c3-c61f-4b95-8b15-f80329fb67d3" class="bulleted-list"><li style="list-style-type:disc">Find：当连通的节点都存储在一个树上，那么判断他们是否连通只需要判断他们的<strong>根节点</strong>是否为同一个。</li></ul><ul id="3215615a-da73-47dc-91ab-216f0ee902b2" class="bulleted-list"><li style="list-style-type:disc">Union：当我们要连通两个节点的时候，需要找寻到他们的<strong>根节点</strong>，并让某一个根节点成为另一个根节点的叶子结点。</li></ul><p id="6579c78b-4416-4af0-a5f7-3b483a8df444" class="">是的，Find &amp; Union 都需要有一个找寻梗节点的方法所以我们先实现找寻根节点的方法，我们只需要不断找寻某个节点的父节点，并继续找寻父节点的父节点直到父节点是他本身。</p><pre id="34824fa8-f624-4276-abee-e4192f856e62" class="code code-wrap"><code>private int findRoot(int p) {
    while (p != id[p]) {
        p = id[p];
    }
    return p;
}</code></pre><p id="6d411d83-df1a-474a-b24d-a1f339ca98d0" class="">Find：我们只需要找寻到 <code>节点q</code> 的根节点 和 <code>节点p</code> 的根节点，并比较他们是否是同一个节点即可。</p><pre id="eecf1448-ad29-445b-8449-0864964d1a43" class="code"><code>@Override
public boolean connected(int p, int q) {
    return findRoot(p) == findRoot(q);
}</code></pre><p id="68688141-e9bd-483a-be51-af9c53e377c0" class="">Union：我们找寻到 <code>节点q</code> 的根节点 和 <code>节点p</code> 的根节点，并放 <code>节点p</code> 的根节点的父节点设置为 <code>节点q</code> 的根节点即可。</p><pre id="aecf71d0-18bb-4744-9523-86b301c177d8" class="code code-wrap"><code>@Override
public void union(int p, int q) {
    int proot = findRoot(p);
    int qroot = findRoot(q);
    id[proot] = qroot;
}
</code></pre><h3 id="f7fb073e-6041-43c8-ae21-2229593fcb37" class="">复杂度分析</h3><p id="6684e77c-fd8e-44b2-a5a9-d054556bf815" class="">空间复杂度：由于需要 N 个空间存储每个节点所在的集合，所以空间复杂度就是 On</p><p id="df5d544f-f015-4f56-bb58-847d7405c510" class="">时间复杂度分析如下</p><table id="9941921d-fdc2-4b30-8d9f-0b8504c4329f" class="simple-table"><tbody><tr id="347a0cca-86dd-4b79-ad7d-702eaba0f18e"><td id="bwCx" class="">Init</td><td id="gU:E" class="">Union</td><td id="VmKf" class="">Find</td></tr><tr id="dd4d216f-4d12-43f7-ac45-68290ec21278"><td id="bwCx" class="">N</td><td id="gU:E" class="">最快O1 最差On</td><td id="VmKf" class="">最快O1 最差On</td></tr></tbody></table><p id="adeaa559-4cd8-451e-bab7-4573e78b9c66" class="">Init：初始化的时候需要遍历一遍数组，所以时间复杂度是 On</p><p id="55da2e3b-ea7e-4ec1-bf75-e9d1c53eee70" class="">Union &amp; Find：从代码可知，这两个方法的实现都关联到 <code>findRoot</code> 方法的时间复杂度。而<code>findRoot</code> 方法时间复杂度是不稳定的。他的时间复杂度，与节点距离根节点的高度有关。当每个节点都是根节点的时候，<code>findRoot</code> 方法的时间复杂度就是 O1，当所有节点都在同一棵树上，并且这个树退化成了链表，那么此时时间复杂度就是 On。</p><blockquote id="3d8f4a42-cba6-42d1-84a4-250cdfb62ccc" class="">On 是怎么诞生的？我们现在有 5 个节点，那么当我们<code>union(0,1)</code>的时候他会形成一个2层的树，但我们继续 <code>union(0,2)</code> 的时候就会形成一个3层的树，依次类推，N 个节点最终会形成一个 N 层的树，此时树退化成了链表。<figure id="24f937c9-e3a3-4ee4-85bf-91bd5f2a9b8b" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%207.png"><img style="width:672px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%207.png"/></a></figure><div id="a030c5a7-24eb-4df9-b0b0-1a17480285d9" class="column-list"><div id="edf15195-e899-4c9b-bab0-db2325b60958" style="width:33.33333333333333%" class="column"><figure id="b71261fb-0545-42fe-84bf-4477b2e8d422" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%208.png"><img style="width:240px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%208.png"/></a></figure></div><div id="324a0f27-a409-4ecc-bf5d-cf21a1f28ee5" style="width:33.33333333333333%" class="column"><figure id="db40b7c0-500f-4469-af4f-8f43a5cf126c" class="image" style="text-align:right"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%209.png"><img style="width:288px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%209.png"/></a></figure></div><div id="0c898d51-2861-4048-b95f-bc715070a680" style="width:33.33333333333334%" class="column"><figure id="be965d74-a320-4dec-9ff1-60ccc3343a72" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2010.png"><img style="width:192px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2010.png"/></a></figure></div></div><p id="46b75dc0-67a5-4c02-8f68-5a749902b766" class="">
</p></blockquote><p id="517ee842-3576-4bbe-be79-0a44286afb14" class="">
</p><h3 id="3cd1be92-bca3-4cd1-8fd8-eb5e6166d24b" class="">总结</h3><p id="4d17f802-8da3-4d3c-b406-0a7396d33a38" class=""><code>Quick-Union</code> 实现是为了能提高我们合并两个集合的效率，把节点存储在树结构上，可以使得查询只需要访问一条路径上的节点，减少了访问无关节点的访问。虽然 <code>Union &amp; Find</code> 的时间复杂度都是最差 On，看起来好像没有 <code>Quick-Find</code> 实现来的稳定高效，但如果是出现在一个 <code>Union</code> 操作频繁的场景，他带来的收益是客观的。虽然我们提出了一个不稳定的实现，但我们得到了个更高效的模型。</p><pre id="f7a0ceab-23d5-4b31-bb10-3b2013285579" class="code code-wrap"><code>public class QuickUnion implements IDynamicConnectivity{

		private int[] id;
		public QuickUnion(int size) {
		    id = new int[size];
		    for (int i = 0; i &lt; id.length; i++) {
		        id[i] = i;
		    }
		}
		
		@Override
		public void union(int p, int q) {
		    int proot = findRoot(p);
		    int qroot = findRoot(q);
		    id[proot] = qroot;
		}
		
		@Override
		public boolean connected(int p, int q) {
		    return findRoot(p) == findRoot(q);
		}
		
		// 最坏 On 的查找时间
		private int findRoot(int p) {
		    while (p != id[p]) {
				    p = id[p];
		    }
		    return p;
    }
}</code></pre><h2 id="51c11d12-e09e-41db-8011-fd19547ed42a" class="">Weighted Quick-Union</h2><p id="6a78c74c-af27-4da5-9221-d3aa1ae256a8" class="">在刚刚我们一起实现完 <code>Quick-Union</code> 后，得到了一个不稳定的最差时间复杂度为 On 的 <code>Union &amp; Find</code> 实现，我们知道影响这个时间复杂度的核心原因是树的层数，很快我们就能想到优化数的层数，以达到优化找寻到根节点的时间复杂度。</p><h3 id="041d1b8c-eaa0-4b34-abaa-523bd9ea7579" class="">干掉On</h3><figure id="63cb5699-3467-4571-86b2-da7205e4fa32" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2010.png"><img style="width:192px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2010.png"/></a></figure><p id="abbd90d5-6b48-4a35-b678-25297ab2e209" class="">在 <code>Quick-Union</code> 的形成 On 的原因其实很好理解，聪明的你也肯定想到了解决的办法。那就是反过。让那个独立的树合并进大的树。这样即使合并完所有的节点，树的层数也是2层，当我们只有 5 个节点的时候不明显，但是如果 N = 1000000 呢？原先的 <code>Quick-Union</code> 需要 1000000 次向上查找才能查找到根节点，而这种方式，只需要 2 次，优化效果显著。</p><figure id="0e9fc50e-0fe9-4971-b281-eb0f13657a20" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2011.png"><img style="width:624px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2011.png"/></a></figure><h3 id="a7c77ab3-2cda-4341-a094-c827ca9a3593" class="">枝繁叶茂</h3><p id="209c13bd-60e3-4819-8e44-13b329fab778" class="">利用刚刚优化的思想，我们很容易相当到，合并两个树的时候，当哪个树拥有的节点数量更多的时候，让他成为另一个的节点的父节点。因此我们需要一个结构存储这个根节点包含的节点数量，我们使用一个 <code>int[] sz</code> 数组存储每个节点包含的节点数量。当我们合并两个节点，如 <code>节点big </code>和 <code>节点small</code> 的时候，<code>sz[big] = sz[big] + sz[small]</code> 。</p><p id="01db9fb1-a981-4ae8-b760-50d8c2426ea9" class="">Init：由于加入了新的 <code>sz</code> 数组我们的初始化也要初始化 <code>sz</code> 数组，初始状态下，每个节点都是独立的根节点，每个节点只包含他一个节点。</p><pre id="ea5fa7a4-9c57-40d1-a4a7-ffe5c5e69de5" class="code code-wrap"><code>public class WeightedQuickUnion implements IDynamicConnectivity {
    private int[] id;
    private int[] sz;
    public WeightedQuickUnion(int size) {
        id = new int[size];
        sz = new int[size];
        for (int i = 0; i &lt; id.length; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }
}</code></pre><p id="1fa74120-b8a4-4362-9509-7e5446dd7fea" class="">Union：当合并两个节点的时候，需要比较他们的所包含的节点数量，让小根节点成为大根节点的叶子节点。并更新大根节点所包含的节点数量。</p><pre id="8b187b6c-d2ff-43a6-9399-120ec4a2abeb" class="code code-wrap"><code>@Override
public void union(int p, int q) {
    int proot = findRoot(p);
    int qroot = findRoot(q);
    if (sz[proot] &lt; sz[qroot]) {
        id[proot] = qroot;
        sz[qroot] += sz[proot];
    } else {
        id[qroot] = proot;
        sz[proot] += sz[qroot];
    }
}</code></pre><p id="e777548c-7c56-486a-a777-46438428d996" class="">Find &amp; findRoot： 没有变化。</p><pre id="7fac7d25-e665-48c5-afa1-f0e42abaf805" class="code"><code>@Override
public boolean connected(int p, int q) {
    return findRoot(p) == findRoot(q);
}

private int findRoot(int p) {
    while (p != id[p]) {
		    p = id[p];
    }
    return p;
}</code></pre><h3 id="83524db6-0d7d-4340-b529-b62d4c9d1044" class="">复杂度分析</h3><p id="0b3eccf0-6362-49ff-90e4-57245651530b" class="">空间复杂度：由于需要 N 个空间存储每个节点所在的集合，所以空间复杂度就是 On</p><p id="66bf46db-5d3a-4d99-bba8-80eb9866feae" class="">时间复杂度分析如下</p><table id="d06c3297-f1b3-482c-b28b-8482c11e8356" class="simple-table"><tbody><tr id="eda518ee-5545-44bb-ad16-787761620516"><td id="bwCx" class="">Init</td><td id="gU:E" class="">Union</td><td id="VmKf" class="">Find</td></tr><tr id="d5ac8499-6411-4d0d-ace7-4fd6114ca7d0"><td id="bwCx" class="">N</td><td id="gU:E" class="">最快O1 最差OlgN</td><td id="VmKf" class="">最快O1 最差OlgN</td></tr></tbody></table><p id="66d1b3a9-6a8e-448d-b088-b36906c0d7b2" class="">Init：初始化的时候需要遍历一遍数组，所以时间复杂度是 On</p><p id="a4d7fd91-8785-4edd-95f5-423a8ecb0ed2" class="">Find &amp; Union：和 <code>Quick-Union</code> 一样，<code>Find &amp; Union</code> 的时间复杂是由 <code>findRoot</code> 方法决定的，确切来说是由树的层数决定的。在我们优化后的 <code>Union</code> 实现，他只会在一种情况下出现树的层数变大，那就是两个根节点的层数相同，小根节点成为大根节点叶子节点，而导致大根节点的层数增加。</p><div id="8303a492-1d3f-414a-a546-320e818e95c7" class="column-list"><div id="73cfdd6b-c62a-43b2-ae5b-6aba86a82908" style="width:50%" class="column"><figure id="41fdedf7-3348-46ab-9a94-309c4fa23cad" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2012.png"><img style="width:700px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2012.png"/></a></figure></div><div id="d17d90d2-8a4c-4412-818d-c62d64fb08b3" style="width:50%" class="column"><figure id="20ac7f93-c4a5-4cff-adf7-77147b82854b" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2013.png"><img style="width:336px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2013.png"/></a></figure></div></div><p id="fa48ea7a-c208-4417-8d83-0fe72fc20cf5" class="">那么节点的层数怎么计算？我们不难发现，我们可以粗浅的认为，但出现节点层数增加的时候，大根节点所包含的节点数量是翻倍的。我们假设有 N 个节点，我们通过 <code>Union</code> 操作使得所有的节点合并成了一个树，那么他最多发生 x 次翻倍，也就是 <code>2^x = N</code>，得到 <code>x = lgN</code> ，而翻倍一次层数+1，可以粗浅的认为这棵树最多有 <code>x = lgN</code> 层。所以 <code>findRoot</code> 的时间复杂度为 lgN。</p><h3 id="f3911be3-2023-4a39-8341-f7b4d013ca70" class="">路径压缩</h3><p id="5e3603a0-8370-4fdd-b005-bb6d15914dde" class="">我们仔细想想，其实对于同一个根下的节点，他们的关系都是一样的，就是他们都在一个集合中，只要他最终的根节点还是那个根节点就行。至于他的父节点？只要是这个树下的任何一个节点都行。那我们其实在 <code>findRoot</code> 的过程就可以想到，把这条路径进行压缩，以减小树的层数。</p><div id="20d06fc0-2d6d-463d-a54e-a636877074d6" class="column-list"><div id="c20adcb7-3940-4cca-a5e9-49e4354f00db" style="width:50%" class="column"><figure id="71b6c381-97c5-415e-a280-fa3d8f7d8922" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2013.png"><img style="width:336px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2013.png"/></a></figure></div><div id="dcc66e28-7ecd-4c86-8c4a-59d7118e356d" style="width:50%" class="column"><figure id="6bca73c4-13d9-4d24-b61d-e6af5f58719d" class="image"><a href="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2014.png"><img style="width:754px" src="1%20%E8%8D%89%E5%B1%A5%E8%99%AB%E9%83%BD%E8%83%BD%E7%9C%8B%E6%87%82%E7%9A%84%E5%B9%B6%E6%9F%A5%E9%9B%86%200b174f5ef85746e4984a6f0e547f60f4/Untitled%2014.png"/></a></figure></div></div><p id="1c0fb2fb-78eb-482d-9079-fec8423e8ae4" class="">而压缩的办法呢？那就是更新我们所遇到的节点的父节点为祖父节点。</p><pre id="99164c9e-a688-40a7-9e1e-07bedd796be1" class="code code-wrap"><code>private int findRoot(int p) {
    while (p != id[p]) {
				//路径压缩，节点的父节点，变成祖父节点相当于减少了一层。
				id[p] = id[id[p]];
        p = id[p];
    }
    return p;
}</code></pre><p id="13a10907-bae9-424c-ad34-b71aed03f941" class="">如经过路径压缩，我们使得节点的层数减半。那么最后层数是lg（lg N）也就是lg*N。</p><h3 id="2b8b0fc5-655d-4479-b596-27c4b7c19e83" class="">总结</h3><p id="fa6db1eb-079f-4686-8c86-008182472304" class="">我们最后通过加权和路径实现枝繁叶茂，而压缩了层数，提高了 <code>findRoot</code> 的效率，得到了一个高效的并查集算法。</p><pre id="b1b6517e-eaf5-4f87-8130-050cebd1a0e6" class="code code-wrap"><code>public class WeightedQuickUnion implements IDynamicConnectivity{

    private int[] id;
    private int[] sz;
    public WeightedQuickUnion(int size) {
        id = new int[size];
        sz = new int[size];
        for (int i = 0; i &lt; id.length; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }

		//每次合并选择深度最小的那个节点合并
		//什么情况下树的深度会加1？当两个节点节点数量一样大的时候深度就会+1
    //此时节点数量翻倍，所以我们假设一个节点最多可以翻x倍
		//得到 2^x = N所以树最大深度是 lgN
		@Override
    public void union(int p, int q) {
        int proot = findRoot(p);
        int qroot = findRoot(q);
        if (sz[proot] &lt; sz[qroot]) {
            id[proot] = qroot;
            sz[qroot] += sz[proot];
        } else {
            id[qroot] = proot;
            sz[proot] += sz[qroot];
        }
    }

    @Override
    public boolean connected(int p, int q) {
        return findRoot(p) == findRoot(q);
    }

		//由于 union保证了树深 lgN所以 findRoot最差情况是 lgN
		private int findRoot(int p) {
        while (p != id[p]) {
						//路径压缩，节点的父节点，变成祖父节点相当于减少了一层。
						id[p] = id[id[p]];
            p = id[p];
        }
        return p;
    }
}
</code></pre></div></article></body></html>